package com.algorithm.learning.base.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/24 22:09
 **/
public class 从底层到上层获取树的每层数据 {

    public static class TreeNode {
        private TreeNode left;
        private TreeNode right;
        private int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * 所谓从底层到上层获取每层的数据，意思如下：
     *
     * 假如有一个二叉树：
     *           a
     *        ↙     ↘
     *       b       e
     *     ↙   ↘     ↙
     *    d     c   f
     *               ↘
     *                 g
     *
     *  我们需要把这颗树的每一层都打印出来，并且从底层打印：
     *  [g], [d,c,f],[b,e],[a]
     *
     *  最终的数据结构结果就是List套List：[[g], [d,c,f],[b,e],[a]]
     *
     *  这道题的解题思路可以借助于队列，
     *  假如我们不考虑从底层开始，我们就从树的根节点开始，将每一层放入集合中，那么利用队列如何做？
     *  其实步骤总共就两步：
     *  1、首先我们把节点，放入队列中，此时再根据队列的size，弹出对应size的节点，然后放入集合中
     *  2、在弹出节点的同时，再把节点的左右子节点，放入队列中，
     *  重复1、2的步骤，直到队列为空，那么此时集合中的数据就是从底层到上层的每层数据了。
     *
     * 但是根据上面的步骤，最终的结果是从根节点到底层的，不符合题意？依然有两种方式解决：
     * 1、根据上面的步骤，将最后的结果进行反转
     * 2、我们利用LinkedList, 每次都把结果放在上一个结果的前面即可。
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return null;
        }
        LinkedList<List<Integer>> result = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0) {
                TreeNode treeNode = queue.poll();
                if (treeNode != null) {
                    list.add(treeNode.value);

                    queue.add(treeNode.left);
                    queue.add(treeNode.right);
                }
                size--;
            }
            if (!list.isEmpty()) {
                result.addFirst(list);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        List<List<Integer>> lists = levelOrderBottom(root);
        System.out.println(lists);

    }
}
